package com.demo.algorithm;

/**
 * Created by hunter
 *
 * @Description 快速排序, 找到一个基数(一般取第一个值), 先从后往前到start比较, 找到比它小的值就与此值交换位置且记录end值结束,
 * 再从前往后到end再比较, 找到比它大的值再交换且记录start值结束, 直到end值小于start值
 */
public class QuickSort {

    public static void sort(Integer[] numbers, int start, int end) {
        if (numbers == null || numbers.length == 0 || start >= end) {
            return;
        }

        int tempStart = start;
        int tempEnd = end;
        int baseVal = numbers[start];
        while (start < end) {

            for (int i = end; i > start; i--) {
                if (numbers[i] < baseVal) {
                    end = i;

                    int tempVal = numbers[start];
                    numbers[start] = numbers[end];
                    numbers[end] = tempVal;

                    break;
                }

                end--;
            }

            for (int i = start; i < end; i++) {
                if (numbers[i] > baseVal) {
                    start = i;

                    int tempVal = numbers[end];
                    numbers[end] = numbers[start];
                    numbers[start] = tempVal;

                    break;
                }

                start++;
            }
        }

        print(numbers);
        System.out.println("~!~~~~~~~~~~~~~~~~~");

        sort(numbers, tempStart, end);
        sort(numbers, end + 1, tempEnd);
    }

    public static void main(String[] args) {
        Integer[] numbers = {4, 7, 5, 3, 1, 8, 2, 8, 9};
        // Integer[] numbers = {1, 3, 7, 5, 1, 9, 2, 4};
        sort(numbers, 0, numbers.length - 1);
        print(numbers);
    }

    private static void print(Integer[] numbers) {
        for (Integer i : numbers) {
            System.out.println(i);
        }
    }
}
